#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/

#define STACK_MAX_SIZE 100 // 栈最多支持存放100个数据元素

#define bool int

/*算符间的优先关系表(+,-,*,/,(,),#)*/
char cpri[7][7] = {
	 {'>','>','<','<','<','>','>' },
	 {'>','>','<','<','<','>','>' },
	 {'>','>','>','>','<','>','>' },
	 {'>','>','>','>','<','>','>' },
	 {'<','<','<','<','<','=',' '},
	 {'>','>','>','>',' ','>','>'},
	 {'<','<','<','<','<',' ','='}
};

/*定义栈的函数*/
typedef struct stack {
	int* base;
	int* top;
	int number_of_elements; // 栈内实际数据元素个数
} *Stack;

// 初始化名为s的栈，初始化成功，返回0，否则返回1。
int init_stack(Stack* s) {
	(*s) = (Stack)malloc(sizeof(Stack));
	(*s)->base = (int*)malloc(STACK_MAX_SIZE * sizeof(int));
	if (!(*s)->base)
		return 1;  //存储分配失败，返回error
	(*s)->top = (*s)->base;  //分配成功则让栈顶指针指向栈底指针
	(*s)->number_of_elements = STACK_MAX_SIZE;
	return 0;
}

// 只返回栈顶元素，通过result变量返回栈顶元素的值。函数返回值用于表示执行状态：0，成功；1，不成功。
int get_top(Stack s, char* symbol) {
	//int result; 
	if (s->top == s->base) {
		return 1;
	}
	(*symbol) = *(s->top);
	return 0;
}

// 入栈。返回值表示是否压栈成功：0，成功；1，不成功。
int push(Stack s, char operator_or_operand) {
	if (s->top - s->base >= s->number_of_elements) {
		return 1;
	}
	*(++s->top) = operator_or_operand;
	//(s->top)++;
	return 0;
}

int pop(Stack s, char* p_operator_or_operand) {
	if (s->top == s->base) {//判断是否栈空
		return 0;
	}
	*p_operator_or_operand = *(s->top);
	s->top--;
	return 1;
}

// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
int is_optr(char symbol) {
	switch (symbol) {
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':
	case '#':
		return 1;
	default: return 0;
	}
}

/*返回运算符在数组中的索引*/
int demo(char c) {
	int in;
	switch (c) {
	case '+': in = 0; break;
	case '-': in = 1; break;
	case '*': in = 2; break;
	case '/': in = 3; break;
	case '(': in = 4; break;
	case ')': in = 5; break;
	case '#': in = 6; break;
	default: return -1;
	}
	return in;
}

/*运算符优先级的判定*/
char precede(char top, char c)
{
	int i, j;
	i = demo(top);
	j = demo(c);
	return cpri[i][j];
}

//运算函数
char operate(char a, char theta, char b)
{
	int a1, b1;
	char result = 0;
	a1 = a - '0';
	b1 = b - '0';

	switch (theta)
	{
	case '+':
		result = (char)((a1 + b1) + '0');
		break;
	case '-':
		result = (char)((a1 - b1) + '0');
		break;
	case '*':
		result = (char)((a1 * b1) + '0');
		break;
	case '/':
		result = (char)((a1 / b1) + '0');
		break;
	}
	return result;
}


// 判断刚扫描到的symbol是否操作符。如果symbol是操作符，返回1，否则返回0。
bool is_operator(char symbol) {
	if (symbol == '+' || symbol == '-' || symbol == '*' || symbol == '/' ||
		symbol == '(' || symbol == ')' || symbol == '#') {
		return 1;
	}
	return 0;
}

// 判断刚扫描到的symbol是否操作数。如果symbol是操作数，返回1，否则返回0。
bool is_operand(char symbol) {
	if (symbol >= '1' && symbol <= '9') {
		return 1;
	}
	return 0;
}

// 用于计算表达式的值，比如#3*(2+6)/4#。
// 返回值表示求值状态：0，合法表达式，成功求值；1，表达式不合法。
// result变量用于返回计算结果。
int evaluate(char* expression, int* result)
{
	int k = 1;
	char c = 0, theta = 0;
	char e = 1;
	char a = 0, b = 0;
	Stack OPND;
	Stack OPTR;
	init_stack(&OPTR);
	init_stack(&OPND);
	c = expression[k];
	k++;
	push(OPTR, expression[0]);
	while (expression[k] != '#' || e != '#') {
		if (is_operand(c)) {
			push(OPND, c);
			c = expression[k]; //读取下一字符c = '#'
			if (c != '#') {
				k++;
			}
		}
		if (is_operator(c)) {
			get_top(OPTR, &e);
			switch (precede(e, c))
			{
			case '<':
				push(OPTR, c);
				c = expression[k];//栈顶元素的优先权低//c = '2'
				if (c != '#') {
					k++;//expression[k]=='#'
					get_top(OPTR, &e);
				}
				break;
			case '=': //脱括号并接受下一字符
				pop(OPTR, &c);
				c = expression[k];//c = *
				k++;//expression[k]=='2'
				break;
			case '>': //退栈并将运算结果入
				pop(OPTR, (char*)&theta);
				pop(OPND, (char*)&b);
				pop(OPND, (char*)&a);
				push(OPND, operate(a, theta, b));
				get_top(OPTR, &e);
				break;
			}
		}
		else {
			return 1;
		}
	}
	get_top(OPND, &e);
	*result = e - '0';
	return *result;
}

int main() {
	char* symbol = "#3*(2+6)/4#";
	int result = 0;
	evaluate(symbol, &result);
	printf("%d", result);
	system("pause");

}